package bin_tree.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 求出二叉树的最大宽度
 * @author yuisama
 * @date 2022/02/21 20:12
 **/
public class Num662_BinTreeWidth {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int maxWidth = 0;
        Queue<NodeWithNum> queue = new LinkedList<>();
        queue.offer(new NodeWithNum(root,1));
        while (!queue.isEmpty()) {
            int levelWidth = 0;
            // 当前队列中该层的元素个数
            int size = queue.size();
            // 最左侧的节点编号
            int L = 0;
            // 最右侧的节点编号
            int R = 0;
            for (int i = 0; i < size; i++) {
                NodeWithNum cur = queue.poll();
                if (i == 0) {
                    // node就是最左侧节点
                    L = cur.num;
                }
                if (i == size - 1) {
                    // 此时node就是该层的最后侧节点
                    R = cur.num;
                }
                if (cur.node.left != null) {
                    queue.offer(new NodeWithNum(cur.node.left, cur.num * 2));
                }
                if (cur.node.right != null) {
                    queue.offer(new NodeWithNum(cur.node.right, cur.num * 2 + 1));
                }
            }
            levelWidth = R - L + 1;
            maxWidth = Math.max(levelWidth,maxWidth);
        }
        return maxWidth;
    }
    // 此时我们在层序遍历的过程中会存储每个出现的节点和他的编号，我就创建一个新的类
    // 我们就将TreeNode二次包装，新增一个该节点的值
    private class NodeWithNum {
        // 具体每个二叉树的节点
        TreeNode node;
        // 该节点的编号
        int num;
        public NodeWithNum(TreeNode node, int num) {
            this.node = node;
            this.num = num;
        }
    }
}